package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：二叉树的层级遍历
 * @Author Gavin
 * @date 2022.01.02 08:43
 */
public class tree_6 {
    //Time:O(n) Space:O(n)
    public ArrayList<ArrayList<TreeNode>> solution(TreeNode root){
        if(root==null)return null;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        ArrayList<ArrayList<TreeNode>> result=new ArrayList<>();
        while (!queue.isEmpty()){
            ArrayList<TreeNode> pre=new ArrayList<>();
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode preNode=queue.poll();
                pre.add(preNode);
                if(preNode.left!=null){
                    queue.add(preNode.left);
                }
                if(preNode.right!=null){
                    queue.add(preNode.right);
                }
            }
            result.add(pre);
        }
        return result;
    }
}
